package pers.vic.basics.leetcode;

/**
 * @author Vic.xu
 * @description: 53. 最大子序和 {@literal https://leetcode-cn.com/problems/maximum-subarray/}
 * @date: 2020/12/14 0014 13:55
 */
public class J0053_E_MaxSubArray {
    /*
    给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     */
    public static int maxSubArray(int[] nums) {
        int max = nums[0];
        int curMax = max;
        for (int i = 1; i < nums.length; i++) {
            curMax = Math.max(curMax + nums[i], nums[i]);
            max = Math.max(max, curMax);

        }
        return max;
    }

    /**
     * 动态规划 ：和原来的代码没什么区别
     * @param nums
     * @return
     */
    public static int maxSubArray2(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (dp[i-1] > 0) {
                dp[i] = dp[i-1] + nums[i];
            }else {
                dp[i] = nums[i];
            }
        }
        int res = dp[0];
        for (int i = 1; i < dp.length; i++) {
            if (dp[i] > res) {
                res = dp[i];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        //6
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray2(nums));
    }

}
